package skill;

public class Solution287 {
    public static int findDuplicate(int[] nums) {
        //可以把这个数组看作链表
        //将问题转化为快慢指针
        int slow = 0;
        int fast = 0;

        slow = nums[slow];
        fast = nums[nums[fast]];

        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        //指针相遇，说明有环
        //将慢指针放回0这个初始位置
        //fast依旧放在老位子上
        //然后slow和fast同步移动，直到相遇
        slow = 0;

        while(nums[slow] != nums[fast]){
            slow = nums[slow];
            fast = nums[fast];

        }

        return nums[slow];


    }

    public static void main(String[] args) {
        int [] nums = new int[]{1,3,4,2,2};
        int duplicate = findDuplicate(nums);
        System.out.println("duplicate = " + duplicate);
    }


}
